package leetcode6;

public class test19 {
    /*
    * 搜索二维矩阵 II*/

    //二叉搜索树
//    public boolean searchMatrix(int[][] matrix, int target) {
//        int i = matrix.length - 1, j = 0;
//        while(i >= 0 && j < matrix[0].length)
//        {
//            if(matrix[i][j] > target) i--;
//            else if(matrix[i][j] < target) j++;
//            else return true;
//        }
//        return false;
//    }
    /*
    * 二分*/
    public boolean searchMatrix(int[][] matrix, int target) {
        for(int[] row: matrix){
            int index = search(row,target);
            if(index >= 0){
                return true;
            }
        }
        return false;
    }
    public int search(int[] nums,int target){
        int low = 0;
        int high = nums.length - 1;
        while(low <= high){
            int mid = (high - low ) / 2 + low;
            int num = nums[mid];
            if(num == target){
                return mid;
            }else if(num > target){
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }

        }
        return -1;
    }

}
